import java.util.*;

public class MaxProbability implements Segment {

	public static void main(String[] args)
	{
		Dic.initWordDic();
        Dic.initFrequentDic();
		MaxProbability maxProbability = new MaxProbability();
		maxProbability.segment("形成分子时");
		System.out.println(maxProbability.getResult());
	}
	
	private List<List<WordArc>> adjList; //切分词图，用逆邻接表
	private int[] prevNode; //最佳前驱结点
	private double[] prob; //累计概率
	private boolean[] visited; //切分词语时判断是否访问过的辅助数组
	private String sentence; //要被切分的文本
	public final static int MAXLEN = 3; //最大匹配长度
	private ArrayList<String> result; //分词结果
	
 	public MaxProbability()
	{	
	}
	/**
	 * 生成逆邻接表
	 */
	private void generateList(String text, int start, int end)
	{
		//已经切分完毕
		if(start == end)
		{
			return;
		}
		else
		{
			if(!visited[start])
			{
				visited[start] = true;
				int len=MaxProbability.MAXLEN;
				//判断剩余字符串是否足够切分
				if(end-start<len)
					len = end-start;
				for(int i=len; i>0; --i)
				{
					//开始进行切分匹配
					String word = text.substring(start, start+i);
					if(Dic.matchWord(word))
					{
						//词典里有这个词
						//System.out.println(word);
						WordArc arc=new WordArc(start, end, word);
						arc.selfProb = Dic.getSelfFrequency(word);
						adjList.get(start+i).add(arc); //插入到结尾的地方！ 
					}
					//递归切分
					generateList(text, start+i, end);
				}
			}
		}
	}
	
	/**
	 * 分词
	 */
	public void segment(String str)
	{
		this.sentence = str;
		//初始化最佳前驱结点数组
		prevNode = new int[str.length()+1];
		//初始化累计概率数组
		prob = new double[str.length()+1];
		prob[0] = 1;
		//初始化切分词图
		adjList = new LinkedList<List<WordArc>>();
		for(int i=0; i<=str.length(); ++i)
		{
			adjList.add(new LinkedList<WordArc>());
		}
		//初始化visited辅助数组
		visited = new boolean[str.length()+1];
		//初始化分词结果数组
		result = new ArrayList<String>();
		
		
		//调用generateList
		generateList(sentence, 0, sentence.length());
		
		for(int i=1; i<adjList.size(); ++i)
		{
			getPrev(i);
		}
		generateResult();
	}
	
	/**
	 * 计算节点i的最佳前驱节点，以及计算它的累计概率
	 * @param i
	 */
	private void getPrev(int i)
	{
		Iterator<WordArc> iterator = adjList.get(i).iterator();
		WordArc arc = null;
		int maxIndex = -1;
		double maxProb = Double.NEGATIVE_INFINITY;
		
		while(iterator.hasNext())
		{
			arc=iterator.next();
			double nodeProb = prob[arc.start] * arc.selfProb;
			if(maxProb < nodeProb)
			{
				maxProb = nodeProb;
				maxIndex = arc.start;
			}
		}
		prob[i] = maxProb;
		prevNode[i] = maxIndex;
	}
	/**
	 * 形成切分结果
	 */
	private void generateResult()
	{
		//最佳切分路径
		ArrayList<Integer> road = new ArrayList<Integer>();

		for(int i=adjList.size()-1; i>0; i=prevNode[i])
		{
			road.add(i);
		}
		road.add(0);
		
		for(int i=road.size()-1; i>0; --i)
		{
			result.add(sentence.substring(road.get(i), road.get(i-1)));
		}
	}
	
	/**
	 * 输出分词结果
	 */
	public String getResult()
	{
		StringBuilder ret = new StringBuilder();
		for(int i=0; i<result.size(); ++i)
		{
			ret.append(result.get(i)+"/ ");
		}
		return ret.toString();
	}
	
	static class WordArc
	{
		public int start; //起始位置
		public int end; //结束位置
		public String termText; //词
		public String type; //词性
		public double selfProb; //自身的概率，不取对数
		
		public WordArc(int start, int end, String word)
		{
			this.start = start;
			this.end = end;
			this.termText = word;
		}
	}
	
	
	

}
